{
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.8.3-final"
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1597673290256",
   "display_name": "Python 3.8.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2,
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。\n",
    "\n",
    "示例:\n",
    "```\n",
    "输入: [-2,1,-3,4,-1,2,1,-5,4]\n",
    "输出: 6\n",
    "解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。\n",
    "```\n",
    "进阶:\n",
    "\n",
    "如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。\n",
    "\n",
    "来源：力扣（LeetCode）\n",
    "链接：https://leetcode-cn.com/problems/maximum-subarray\n",
    "著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 思路\n",
    "\n",
    "暴力解法的思路：\n",
    "```\n",
    "循环[0, n]\n",
    "    循环[0, 上层+1]\n",
    "        求最大值\n",
    "```\n",
    "求最大值这部也要循环，但是可以优化，复杂度为`O(n^2)`\n",
    "\n",
    "动态规划：\n",
    "\n",
    "一开始考虑复杂了，在想是不是要用二维数组来记录动态规划，想了半天，还是看了题解，虽然以前还写过，但是忘了。\n",
    "\n",
    "动态转移方程：\n",
    "\n",
    "$$\n",
    "f(i) = max( f(i-1) + a_i, a_i)\n",
    "$$"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import *\n",
    "class Solution:\n",
    "    def maxSubArray(self, nums: List[int]) -> int:\n",
    "        if not nums:\n",
    "            return 0\n",
    "        max_value = nums[0]\n",
    "        tmp = 0\n",
    "        for i in range(len(nums)):\n",
    "            tmp = max(tmp + nums[i], nums[i])\n",
    "            max_value = max(max_value, tmp)\n",
    "        return max_value\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert Solution().maxSubArray([-2,1,-3,4,-1,2,1,-5,4]) == 6"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert Solution().maxSubArray([]) == 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "assert Solution().maxSubArray([-2]) == -2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ]
}